package Algorithm.Tree;

/**
 * @Author cj
 * @Date 2022/5/25 20:23
 */
public class getMaxSearchTree {

    static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int val) {
            this.value = val;
        }
    }

    public static class ReturnType {
        public Node maxBSThead;
        public int maxBSTSize;
        public int min;
        public int max;

        public ReturnType(Node maxBSThead, int maxBSTSize, int min, int max) {
            this.maxBSThead = maxBSThead;
            this.maxBSTSize = maxBSTSize;
            this.min = min;
            this.max = max;
        }
    }

    public Node getMaxBST(Node head) {
        return process(head).maxBSThead;
    }

    private ReturnType process(Node X) {
        if (X == null) {
            return new ReturnType(null, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
        }
        // 得到左树全部信息
        ReturnType lData = process(X.left);
        // 得到右树全部信息
        ReturnType rData = process(X.right);
        /** 信息整合 **/
        // 以X为头节点的子树的最小值
        int min = Math.min(X.value, Math.min(lData.min, rData.min));
        // 以X为头节点的子树的最大值
        int max = Math.max(X.value, Math.max(lData.max, rData.max));
        // 考虑BST在左子树或右子树中
        int maxBSTSize = Math.max(lData.maxBSTSize, rData.maxBSTSize);
        Node maxBSTHead = lData.maxBSTSize > rData.maxBSTSize ? lData.maxBSThead : rData.maxBSThead;
        // 利用以上信息，判断是否是以X为头节点的情况
        if (lData.maxBSThead == X.left && rData.maxBSThead == X.right &&
                lData.max < X.value && X.value < rData.min) {
            maxBSTHead = X;
            maxBSTSize = lData.maxBSTSize + rData.maxBSTSize + 1;
        }
        // 返回
        return new ReturnType(maxBSTHead, maxBSTSize, min, max);
    }
}
